The present invention relates to integrated circuit design and more particularly to inserting repeaters in a single source, multi destination distributed RC network for reducing delay.
Repeater insertion has become an important tool for present day design of integrated circuits (IC). Delays in a long interconnect in an IC can be reduced only to a certain extent by having a large driver. As the signal propagates through the resistive interconnect, signal attenuation causes the delay per unit length to increase. Insertion of the repeaters along the interconnect restore strength of the signal at the output of the repeater to the power rail level, thus reducing delay. Repeater insertion also restores signal strength in nets with a large fan-out in which a single source attempts to drive a large number of destinations, otherwise referred to as sinks. Interconnect delay cannot be reduced indefinitely by inserting a large number of repeaters. This is because the signal experiences an intrinsic delay of the repeater while propagating through the repeater. Thus, there is an optimum number of repeaters which achieves the minimum delay.
As used throughout this disclosure, a repeater is a buffer that can be either inverting or non-inverting. Usually, a pre-designed repeater library is used comprising any number of available buffers with corresponding sizes. Thus, repeater sizes are discrete in the library and are not continuous. Different size repeaters offer different intrinsic delays, input loading and drive capabilities. In a general situation, the most delay reduction is obtained by placing different size repeaters at different places in a net.
A large category of interconnects comprises a single driver that connects to multiple sinks. The topology of the interconnections between a single driver, otherwise referred to as a root or source, and the sinks to which the root is connected is usually referred to as a tree. Repeater insertion into a tree structure may be achieved by solving two sub problems. The first problem is locating places along the tree where repeaters will be placed. The second problem is determining the sizes of the repeaters to be placed at the selected locations.
One researcher has proposed a dynamic programming methodology for inserting repeaters in a tree structure. A bottom-up approach is utilized to select a subset of given locations on the tree to place repeaters. During the bottom-up traversal, candidate locations are visited one by one. At each candidate location, all possibilities are considered such as not placing a repeater or placing a repeater from all of the available sizes. These choices give rise to a partial solution set. A technique is further identified to identify the partial solutions which are sub optimal for the complete solution. The sub optimal solutions are pruned or otherwise rejected. The rest of the solutions are propagated up the tree. The bottom-up traversal is followed up by a top-down traversal which provides the optimal solution.
The technique just described attempts to reduce Elmore delay. Elmore delay is known to be an upper bound for the actual delay in RC networks. The above described technique however fails to adequately account for controlling the signal slew rate or the rise/fall times of the signal. Although minimizing critical delays are important, other factors such as controlling slew rate have become equally critical in today""s sub-micron IC technologies. Repeater insertion helps to maintain good signal slew rate because the inserted repeaters restore signal strength. However, in certain situations, repeater insertion minimizes the delay in a critical path by isolating a non-critical path with a small-sized repeater placed in the non-critical path. As a result, repeater insertion may aggravate signal slew rate. It is important to explicitly consider the signal slew rate while inserting repeaters for minimizing critical delays.
Incorporating slew rate to obtain an accurate delay model is not straight forward. Slew must be propagated from the input of the driver to the sinks. But since repeaters along the RC tree have not yet been placed and sized, an input slew cannot be propagated.
Extension to the above described method have been proposed to include slew rate. In one technique, repeater sizes and wire widths are considered simultaneously to optimize the Elmore day. The basic algorithm is extended to include slew rate and to optimize power. Although the slew rate is not computed explicitly, the contribution of non-zero slew in the delay model is incorporated. The slew rate at the input of a given stage is assumed to be proportional to the delay in the previous stage. The slew rate is incorporated by adding an additional delay component that is a function of the delay in the previous stage and the repeater size in the current stage. The slew model, however, introduces additional complication in the basic algorithm. The delay in the previous stage is not known during a bottom-up traversal of the tree. Thus identifying and eliminating sub optimal solutions must be deferred thereby increasing the memory and run time complexity.
Other approaches to include slew rate have been proposed. In one solution, a moment based accurate delay model is used to allow for slew. However, since the slew is not known at the input of a repeater being inserted at a candidate location, it is assumed that the input slew is a given constant. This technique is determined to be inadequate since it is known that slew is variable and not constant. Another more rigorous approach was also proposed. Moment based computations are utilized to obtain transfer functions and loading effects for accurate RC modeling. Transfer functions are computed in a bottom-up traversal for different segments of the RC tree. Since the delay due to these accurate transfer functions are not additive, unlike the Elmore delay, convolution of transfer functions are needed to obtain a delay in a path containing more than a single segment. Furthermore, since slew rate at the input of a repeater is not known, the delay is computed for an array of slew rate values. Thus, pruning sub optimal solutions must be deferred. This technique, therefore, is not desirable since it is computation intensive requiring substantial computer resources for circuits of any significant size.
It is desired to provide a technique to place repeaters in a network to reduce delay and properly account for slew rate. It is desired to provide an approach that is not computationally intensive. Further, it is desired to reduce the number of inserted repeaters to a practical level, since repeaters consume valuable power and real estate on the IC.